package cn.lintcode;

/**
 * @author labvi
 * @version 1.0.0
 * 按给定值划分链表
 */
public class PartitionList {

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public static ListNode partition(ListNode head, int x) {
        // write your code here
        if (null == head) {
            return head;
        }


        ListNode leftDummy = new ListNode(0);
        ListNode rightDummy = new ListNode(0);
        ListNode left = leftDummy, right = rightDummy;

        while (head != null) {
            if (head.val < x) {
                left.next = head;
                left = head;
            } else {
                right.next = head;
                right = head;
            }
            head = head.next;
        }

        right.next = null;
        left.next = rightDummy.next;
        return leftDummy.next;
    }

    public static void main(String[] args) {

        //5->-5->0->-8->3->8->-8->0->-1->3->-8->7->-4->-8->2->5->9->4->-5->-6->null
        int[] nums = {5,-5,0,-8,3,8,-8,0,-1,3,-8,7,-4,-8,2,5,9,4,-5,-6};
        ListNode first = new ListNode(5);
        ListNode cur = first;
        for (int i = 1; i < nums.length; i++) {
            cur.next = new ListNode(nums[i]);
            cur = cur.next;
        }
        ListNode partition = partition(first, -4);
        while (partition != null){
            System.out.println(partition.val);
            partition = partition.next;
        }
    }
}
